#include<iostream>
#include<vector>

using namespace std;

//找到特定数在数组中第一次出现的位置和最后一次出现的位置
class Solution {
    private:
    vector<int> res{-1,-1};
public:
    int Bin_Sea(vector<int>& nums1,int left,int right,int target)
    {
        int mid=(left+right)>>1;
        while(left<right)
        {
            if(nums1[mid]>target)
            right=mid-1;
            else if(nums1[mid]<target)
            left=mid+1;
            else 
            break;

            mid=(left+right)>>1;
        }
        if(left>right||nums1[mid]!=target)
        return -1;

        return mid;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
        return res;
        int left=0,right=nums.size()-1;
        int first=-1,last=-1;
    
            first=last=Bin_Sea(nums,left,right,target);
            if(first==-1&&last==-1)
            {
                return res;
            }
            while(first-1>=0&&nums[first-1]==target)
            first=Bin_Sea(nums,left,first-1,target);

            while(last+1<nums.size()&&nums[last+1]==target)
            last=Bin_Sea(nums,last+1,right,target);
            res.clear();
            res.push_back(first);
            res.push_back(last);
            
            return res;
    }
};

